package com.kaizen.leet94;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

/**
 * 94.给定一个二叉树，返回它的中序 遍历。
 *
 * 示例:
 *
 * 输入: [1,null,2,3]
 *    1
 *     \
 *      2
 *     /
 *    3
 *
 * 输出: [1,3,2]
 * 进阶: 递归算法很简单，你可以通过迭代算法完成吗？
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @author kaizen
 * @date 2020/4/23 23:48
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class SolutionKaizen {

    private Stack<TreeNode> stack = new Stack<>();

    /**
     * 迭代算法
     * 栈后法。即先入栈，再访问。
     * 若存在则将该节点放入栈中，再将当前结点设置为结点的左孩子，
     * # 若不存在则取栈顶元素为cur，当且仅当栈空cur也为空，循环结束。
     */
    public List<Integer> inorderTraversal1(TreeNode root) {
        if (root == null) {
            return Collections.emptyList();
        }
        TreeNode curr = root;
        List<Integer> res = new ArrayList<>();
        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }else {
                curr = stack.pop();
                res.add(curr.val);
                curr = curr.right;
            }
        }
        return res;
    }

    /**
     *
     * 递归算法
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal2(TreeNode root) {
        if (root == null) {
            return Collections.emptyList();
        }
        List<Integer> res = new ArrayList<>();
        inorderTraversal(root, res);
        return res;
    }

    /**
     * 中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。
     * 递归算法
     * @param node
     * @param res
     */
    private void inorderTraversal(TreeNode node, List<Integer> res) {
        if (node == null) {
            return ;
        }
        if (node.left != null) {
            inorderTraversal(node.left, res);
        }
        res.add(node.val);
        if (node.right != null) {
            inorderTraversal(node.right, res);
        }
    }


    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
}
